package com.owen.l4;

/**
 * 给定两个大小为 m 和 n 的正序（从小到大）数组nums1 和nums2。请你找出并返回这两个正序数组的中位数。
 *
 * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
 *
 * 
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 *
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 * 示例 3：
 *
 * 输入：nums1 = [0,0], nums2 = [0,0]
 * 输出：0.00000
 * 示例 4：
 *
 * 输入：nums1 = [], nums2 = [1]
 * 输出：1.00000
 * 示例 5：
 *
 * 输入：nums1 = [2], nums2 = []
 * 输出：2.00000
 * 
 *
 * 提示：
 *
 * nums1.length == m
 * nums2.length == n
 * 0 <= m <= 1000
 * 0 <= n <= 1000
 * 1 <= m + n <= 2000
 * -106 <= nums1[i], nums2[i] <= 106
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MySolution1 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] join=join(nums1, nums2);
        int length = join.length;
        if(length%2==0){
            return (join[length/2-1]+join[length/2])/2.0;
        }
        return join[length/2];
    }

    private int[] join(int[] nums1,int[] nums2){
        int[] result=new int[nums1.length+nums2.length];
        int i=0,j=0,k=0;
        for (;  i<nums1.length && j<nums2.length ; ) {
            if(nums1[i]>nums2[j]){
                result[k]=nums2[j];
                j++;
            }else{
                result[k]=nums1[i];
                i++;
            }
            k++;
        }
        if(i>=nums1.length && j<nums2.length){
            for (; j < nums2.length; j++) {
                result[k]=nums2[j];
                k++;
            }
        }
        if(i<nums1.length && j>=nums2.length){
            for (; i < nums1.length; i++) {
                result[k]=nums1[i];
                k++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = {2}, nums2 = {};
        double medianSortedArrays = new MySolution1().findMedianSortedArrays(nums1, nums2);
        System.out.println(medianSortedArrays);
    }

}
